mod bucket;
mod util;
use std::fmt;
use std::convert::From;
use std::iter::repeat;
use std::error::Error as StdError;
use std::hash::{Hash, Hasher};
use std::marker::PhantomData;
use std::collections::hash_map::DefaultHasher;
use std::mem;
#[cfg_attr(feature = "dev", feature(plugin) )]
#[cfg_attr(feature = "dev", plugin(clippy) )]
//序列化
use rand::Rng;
use serde_derive::{Serialize, Deserialize};
use crate::util::{get_alt_index, FaI, get_fai};
use crate::bucket::{Bucket, FingerPrint, BUCKET_SIZE, FIGERPRINT_SIZE};

pub const MAX_RELOCATION: u32 = 100;
pub const DEFAULT_CAPACITY: usize = (1 << 20) - 1;

//错误处理
#[derive(Debug)]
enum CuckooError {
    NotEnoughSpace,
}

//添加打印输出功能
impl fmt::Display for CuckooError {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.write_str("NotEnoughSpace")
    }
}

impl StdError for CuckooError {
    fn description(&self) -> &str {
        "Not enough space to save new element, operation failed!"
    }
}
//布谷鸟过滤器
pub struct CuckooFilter<H> {
    buckets: Box<[Bucket]>, //桶
    len: usize, //长度
    _phantom: PhantomData<H>,
}

//添加默认值功能
impl Default for CuckooFilter<DefaultHasher> {
    fn default() -> Self {
        Self::new()
    }
    
}
impl CuckooFilter<DefaultHasher> {
    pub fn new() -> Self{
        Self::with_capacity(DEFAULT_CAPACITY)
    }
}

impl<H: Hasher + Default> CuckooFilter<H>  {
    pub fn with_capacity(cap: usize) -> Self {
        let capacity = match cap.next_power_of_two() / BUCKET_SIZE {
            0 => 1,
            cap => cap,
        };
        Self {
            buckets: repeat(Bucket::new()) //构建capacity个Bucket
                     .take(capacity)
                     .collect::<Vec<_>>()
                     .into_boxed_slice(),
            len: 0,
            _phantom: PhantomData,
        }
    }
    //尝试插入
    
    fn insert<T: ?Sized + Hash>(&mut self, elem: &T) -> Result<(), CuckooError> {
        let fai = get_fai::<_, H>(elem);
        if self.put(fai.fp, fai.i1) || self.put(fai.fp, fai.i2){
            return Ok(());
        }
        //插入数据冲突,重定位
        let len = self.buckets.len();
        let mut rng = rand::thread_rng();
        let mut i = fai.random_index(&mut rng);
        let mut fp = fai.fp;
        for _ in 0..MAX_RELOCATION {
            let other_fp;
            {
                let loc = &mut self.buckets[i % len]
                                   .buffer[rng.gen_range(0,BUCKET_SIZE)];
                other_fp = *loc;
                *loc = fp;
                i = get_alt_index::<H>(other_fp, i);
            }
            if self.put(other_fp, i) {
                return Ok(());
            }
            fp = other_fp;
        }
        Err(CuckooError::NotEnoughSpace)
    }
    /// Adds `elem` to the filter if it does not in the filter yet.
    /// Returns `Ok(true)` if `elem` was not yet present in the filter and added
    /// successfully.
    fn test_and_insert<T: ?Sized + Hash>(&mut self, elem: &T) -> Result<bool, CuckooError> {
        if self.contains(elem) {
            Ok(false)
        } else {
            match self.insert(elem) {
            Ok(_) => Ok(true),
            Err(e) => Err(e),
            }
        }
    }  
    pub fn len(&self) -> usize {
        self.len
    }
    
    pub fn export(&self) -> ExportedCuckooFilter {
         self.into() 
    }
    pub fn memory_usage(&self) -> usize {
    mem::size_of_val(self) + self.buckets.len() * mem::size_of::<Bucket>()
    }
    pub fn is_empty(&self) -> bool {
    self.len == 0
    }
    fn values(&self) -> Vec<u8> {
       self.buckets
           .iter()
           .flat_map(|b| b.get_fp_data().into_iter())
           .collect()
    }
    fn put(&mut self, fp: FingerPrint, i: usize) -> bool {
         let len = self.buckets.len();
        if self.buckets[i % len].insert(fp) {
            self.len += 1;
            true
        } else {
            false
        }
    }

    pub fn delete<T: ?Sized + Hash>(&mut self, elem: &T) -> bool {
        let FaI {fp, i1, i2} = FaI::from_data::<_, H>(elem);
        self.remove(fp, i1) || self.remove(fp, i2)
    }

    fn remove(&mut self, fp: FingerPrint, i: usize) -> bool {
        if self.buckets[i % self.len].delete(fp){
            self.len -= 1;
            true
        } else {
            false
        }
    }
    pub fn contains<T: ?Sized + Hash>(&self, elem: &T) -> bool {
        let FaI {fp, i1, i2} = get_fai::<T, H>(elem);
        let len = self.buckets.len();
        self.buckets[i1 % len]
            .get_fp_index(fp)
            .or_else(|| {self.buckets[i2 % len].get_fp_index(fp)})
            .is_some()
    }
}
#[derive(Serialize, Deserialize, Debug)]
#[serde(tag="ExpCF")]
pub struct ExportedCuckooFilter {
    #[serde(with = "serde_bytes")]
    pub values: Vec<u8>,
    pub length: usize,
}
impl<H> From<ExportedCuckooFilter> for CuckooFilter<H> {
    fn from (exported: ExportedCuckooFilter) -> CuckooFilter<H> {
    CuckooFilter {
        buckets: exported
                .values
                .chunks(BUCKET_SIZE * FIGERPRINT_SIZE)
                .map(Bucket::from)
                .collect::<Vec<_>>()
                .into_boxed_slice(),
        len: exported.length,
        _phantom: PhantomData,
    }
}
}
impl<H> From<&CuckooFilter<H>> for ExportedCuckooFilter
where
    H: Hasher + Default
    {
    fn from (cuckoo: &CuckooFilter<H>) -> ExportedCuckooFilter{
    ExportedCuckooFilter { values: cuckoo.values(), length: cuckoo.len(), }
    }
}
#[cfg(test)]
mod test {
    use super::*;
    
    #[test]
    fn test_cf_insert(){
        let words = vec!["foo", "bar", "xylophone", "milagro"];
        let mut cf = CuckooFilter::new();
        let mut insertions = 0;
        for s in &words{
           if cf.test_and_insert(s).unwrap(){
               insertions += 1;
           }
        }
        assert_eq!(insertions, words.len() );
        assert_eq!(cf.len(), words.len() );
    }
    #[test]
    fn cf_interoperability() {
        let total_items = 100; //10_000_000;
        let mut filter = CuckooFilter::<DefaultHasher>::with_capacity(total_items);
        let mut num_inserted: u64 = 0;
        //Fit as many values in as possible, count how many made it in.
        for i in 0..total_items {
            match filter.insert(&i) {
                Ok(_) => num_inserted += 1,
                Err(_) => break,
            }
        }
        // Export the fingerprint data stored in the filter,
        // along with the filter's current length.
        let store: ExportedCuckooFilter = filter.export();
        //create a new filter using the 'recover' method and the values previously exported.
        let recovered_filter = CuckooFilter::<DefaultHasher>::from(store);
        // The range 0..num_inserted are all known to be in the filter.
        //The filters shouldn't return false negatives, and therefore they should all be
        //both filters should also be identical.
        for i in 0..num_inserted {
            assert!(filter.contains(&i));
            assert!(recovered_filter.contains(&i));
        }

        //The range total_items..(2 * total_items) are all known *not* to be in the filter.
        //Every element for which the filter claims that it is contained is therefore a false
        //positive, and both the original filter and recovered_filter should exhibit the same fasle
        //psoitive behaviour.
        for i in total_items..(2 * total_items) {
        assert_eq!(filter.contains(&i), recovered_filter.contains(&i) );
        }
        let mut false_queries: u64 = 0;
        for i in total_items..(2 * total_items) {
             if filter.contains(&i) {
                 false_queries += 1;
            }
        }
        let false_positive_rate = (false_queries as f64) / (total_items as f64);
        println!("elements inserted: {}", num_inserted);
        println!("memory usage: {:.2}KBi",
        (filter.memory_usage() as f64) / 1024.0);
        println!("False positive rate: {}%", 100.0 * false_positive_rate);
        assert!(false_positive_rate < 0.03);

    }
    #[test]
    fn test_cf_serialization() {
        // Just a small filter to test serialization.
        let mut filter = CuckooFilter::<DefaultHasher>::with_capacity(100);

        //Fill a few values.
        for i in 0..50{
            filter.insert(&i).unwrap();
        }
        //export data.
        let store: ExportedCuckooFilter = filter.export();
        //serialize using json(for example, any serde format can be used).
        let saved_json = serde_json::to_string(&store).unwrap();
        //create a new filter from the json string.
        let restore_json: ExportedCuckooFilter = serde_json::from_str(&saved_json).unwrap();
        let recovered_filter = CuckooFilter::<DefaultHasher>::from(restore_json);
        //Check our values exist within the reconstructed filter.
        for i in 0..50 {
            assert!(recovered_filter.contains(&i),
            "Target..... {:?}",
            &saved_json
            );
        }
    }
}
